[DP]bzoj 1079: [SCOI2008]着色方案04 January 2018
【题目描述】
有个木块排成一行,从左到右依次编号为~。你有种颜色的油漆,其中第种颜色的油漆足够涂个木块。 所有油漆刚好足够涂满所有木块,即。相邻两个木块涂相同色显得很难看,所以你希望统计任意两个相邻木块颜色不同的着色方案。
【输入】
第一行为一个正整数,第二行包含个整数。
【输出】
输出一个整数,即方案总数模的结果。
【样例输入】
3
1 2 3
【样例输出】
10
【提示】
的数据满足:
【题解】
我们发现最多只有,于是就会想到这样一个: 定义表示上一次用的油漆在没有用的情况下可以刷个墙,而此时还能刷个的油漆数量有个,能刷个墙的油漆数量有个……能刷个墙的油漆数量有个; 此时考虑转移方程: 如果能刷个墙的油漆数量大于(也就是说除了上一次用的油漆还有油漆可以用),那么就有转移方程(为当前能刷i个墙的油漆数量的个数,):
xxxxxxxxxx
F[L][a][b][c][d][e]+=(Num[L-1]-1)*F[L-1][A][B][C][D][E]
同理,用能刷其他个数的墙的油漆转移方程如下:
xxxxxxxxxx
F[L][a][b][c][d][e]+=Num[p]*F[p][A][B][C][D][E]
初始状态就是F[i][0][0][0][0][0]=1
因为这些量会变化,普通的无法完成,所以就会想到用记忆化,那么最终代码如下:
xxxxxxxxxx
#include<cstdio>
#include<algorithm>
#define tt 1000000007
#define Nxt(Row,p) DFS(Row[5],Row[4],Row[3],Row[2],Row[1],p)%tt
using namespace std;
int k,A[6];
long long F[16][16][16][16][16][6];//F[a][b][c][d][e][L] 方便起见把L后置
long long DFS(int a,int b,int c,int d,int e,int L){
if (F[a][b][c][d][e][L]^0) return F[a][b][c][d][e][L];
long long &Ret=F[a][b][c][d][e][L];
int Row[6]={0,e,d,c,b,a};
if (Row[L-1]>1&&L>1) Row[L-1]--,Row[L-2]++,Ret=(Ret+(Row[L-1])*Nxt(Row,L-1))%tt,Row[L-1]++,Row[L-2]--;
for (int i=1;i<=5;i++){
if (i==L-1) continue;
if (Row[i]>0){
Row[i]--,Row[i-1]++;
Ret=(Ret+(Row[i]+1)*Nxt(Row,i))%tt;
Row[i]++,Row[i-1]--;
}
}
return Ret;
}
int main()
{
scanf("%d",&k);
for (int i=0;i<=5;i++) F[0][0][0][0][0][i]=1;
for (int i=0,x;i<k;i++) scanf("%d",&x),A[x]++;
printf("%d\n",Nxt(A,0)%tt);
return 0;
}